#include<vector>
#include<time.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
//最好情况:基本不需要挪动数据  --O(N)
//最坏情况:每次插入都需要挪动数据: 1 + 2 + 3 +...+n-1 = O(N^2)
void InsertSort(vector<int>& a)
{
    int n = a.size();
    for(int i = 0;i<n-1;i++)  //注意是 i < n-1
    {
        //将x插入到[0,end]的有序区间
        int end = i;//end的范围:[0,n-2]
        int x = a[end+1];
        while(end >= 0)
        { 
            if(a[end] > x) //当x和a[end]相等的时候,x是放在a[end]后面，保证了稳定性
            {
                a[end+1] = a[end];//把end位置的值往后移动
                end-=1;
            }
            else
            {
                break;
            }
        }
        a[end+1] = x;
    }
}

//希尔排序--多了一个预排序  
void ShellSort(vector<int>& v)
{
    int n = v.size();
    int gap = n;
    while(gap > 1)
    {
        //实现多次预排序    多次预排序 (gap > 1) + 直接插入排序 (gap == 1)
        //gap = gap / 3 + 1;
        gap = gap / 2;
        //方法1:多组一锅炖  -> 一个元素一个元素的排好 i++
        /*
        for(int i = 0;i<n-gap;i++)  //仅仅需要处理到n-gap-1下标位置  n-gap-1+gap = n-1刚好是最后一个元素位置  
        {
            int end = i; //end的范围:[0,n-gap-1]
            int x = v[end + gap]; 
            while(end >= 0)
            {
                if(v[end] > x)
                {
                    v[end+gap] = v[end];
                    end -= gap;
                }
                else
                    break;
            }
            v[end+gap] = x;
        }
        */
        //方法2:每一组分别排序 -共排序gap组
        for(int j = 0;j< gap;j++)
        {
            for(int i = j; i < n - gap;i+=gap) //每一组的起始位置为j,每隔gap个位置的元素是当前组别的
            {
                int end = i;   
                int x = v[end+gap];//相隔gap个位置的元素是一组的
                while(end >= 0)
                {
                    if(v[end] > x)
                    {
                        v[end+gap] = v[end];
                        end -= gap;//注意这里是-=gap
                    }
                    else
                        break;
                }
                v[end+gap] = x;
            }
        }
    }
}


//选择排序-一次选择一个数
/*
void SelectSort(vector<int>& v)
{
    int n = v.size();
    int end = n-1;//当前元素应该放到哪个位置
    for(int i = 0;i< n-1;i++) //一共有n个数,只需挑选n-1次,每次让一个元素到准确的位置
    {
        int maxi = 0;
        for(int j = 0;j <= end;j++) //每次在[0,end]挑选最大的数放到end位置
        {
            if(v[j] > v[maxi]) maxi = j;
        }
        swap(v[maxi],v[end]);
        end--;//缩小区间
    }
}
*/
//选择排序--每次选择两个数
void SelectSort(vector<int>& v)
{
    int begin = 0;
    int end = v.size()-1;
    //在[begin,end]区间选择,找出最大的放在end位置,找出最小的放在begin位置,然后缩小区间
    while(begin < end) // begin == end ：说明当前只有一个数了,不需要选择
    {
        int maxi = begin,mini = begin;
        for(int i = begin;i<=end;i++)
        {
            if(v[i] > v[maxi]) maxi = i;
            if(v[i] < v[mini]) mini = i;
        }
        swap(v[begin],v[mini]);
        //注意坑点:当begin和maxi位置一样的时候,会导致错误
        //此时由于begin已经和mini位置交换,所以交换之后,mini位置存放的才是最大值
        //此时需要特判断一下 然后修改maxi的位置
        if(begin == maxi)
            maxi = mini;
        swap(v[end],v[maxi]);
        begin++,end--;//缩小区间
    }
}

//冒泡排序
void BubbleSort(vector<int>& v)
{
    int n = v.size();
    for(int i = 0;i<n-1;i++) //n个元素,只需排序n-1趟,每一趟可以让一个元素到达正确的位置
    {
        bool flag = true;//标记是否已经有序
        for(int j = 0;j<n-1-i;j++) //每一趟可以少比较一个已经排序好的元素 所以减i
        {
            if(v[j] > v[j+1])//前后元素比较,相等的时候是不交换的,所以是稳定的
            {
                flag = false;
                swap(v[j],v[j+1]);
            }
        }
        if(flag) break; //某一轮没有交换,说明已经有序了,不需要再比较
    }
}
//堆排序
//排升序 -> 建大堆,每次把最大的元素放在最后面
void AdjustDown(vector<int>& v,int parent,int n) //n:认为堆中有多少个元素
{
    int child = parent*2+1;
    while(child < n)
    {
        if(child+ 1 < n && v[child+1] > v[child])//选出较大的孩子
            child+=1;
        if(v[child] > v[parent])
        {
            swap(v[child],v[parent]);
            parent = child;//向下迭代
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}
void AdjustUp(vector<int>& v,int child)
{
    int parent = (child-1)/2;
    while(child > 0)
    {
        if(v[child] > v[parent])
        {
            swap(v[child],v[parent]);
            child = parent;//向上迭代
            parent = (child-1)/2;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(vector<int>& v)
{
    int n = v.size();
    //1.向下调整建堆
    // for(int i = (n-1-1)/2 ; i >= 0;i--) //从最后一个节点的父节点开始,以前的节点都要调整
    // {
    //     AdjustDown(v,i,n);
    // }
    //case2：向上调整建堆
    for(int i = 1;i<n;i++)  //第1个元素当作堆中元素,后序的元素依次向上调整
    {
        AdjustUp(v,i);
    }
    //2.调堆
    int end = n-1;//认为堆中的元素个数 && 当前堆顶元素应该被放到的位置
    while(end > 0)
    {
        swap(v[0],v[end]);//堆顶和end位置元素交换
        AdjustDown(v,0,end);//从根节点向下调整
        end--;//缩小范围
    }
}


//如果严格三数取中:对于特殊用例,可能大量区间选key会让你选到较小/较大的数,导致性能下降
//所以结合随机选key进行优化
//[left,right]范围的数进行 三数取中 -> 随机选一个数 + 第一个数 + 最后一个数取中间数
int GetMidIndex(vector<int>& a,int left,int right)
{
    //rand() % A ==>0~A-1
    int mid = left + rand() % (right - left + 1) ; //mid的范围:[begin,begin+end-begin-1 + 1] ==>[begin,end]
    if(a[left] < a[mid])
    {
        if(a[right] < a[left]) //右 < 左 < 中
            return left;
        else if(a[right] > a[mid])  //左 < 中 < 右
            return mid;
        else
            return right;
    }   
    else //a[left] > a[mid]
    {
        if(a[right] > a[left]) //右 > 左 > 中
            return left;
        else if(a[mid] > a[right]) //左 > 中 > 右
            return mid;
        else
            return right;
    }
}
//小区间优化 
void InsertSort_QuickSort(vector<int>& v,int left,int right)
{
    for(int i = left;i<right;i++) 
    {
        int end = i;//end的范围:[left,right-1]
        int x = v[end+1];//将x插入到[0,end]的有序区间
        while(end >= left) //注意：这里最多移动到left！！！并不是0
        {
            if(v[end] > x)
            {
                v[end+1] = v[end];
                end -= 1;
            }
            else
                break;
        }
        v[end+1] = x;
    }
}
//hoare版本
//划分为:keyi的左边比它小,右边比它大
int PartSort1(vector<int>& v,int left,int right)
{
    int mini = GetMidIndex(v,left,right);
    swap(v[mini],v[left]);
    int keyi = left; //注意:这里的keyi是下标
    //左边作为key  -> 右边先走
    while(left < right) //当left == right说明只有一个元素,不需要排序
    {
        
        while(left < right && v[right] >= v[keyi] )//右边找严格比v[keyi]小的
            right--;
        while(left < right && v[left] <= v[keyi]) //左边找严格比v[keyi]大的
            left++;
        if(left < right)
            swap(v[left],v[right]);
    }
    swap(v[left],v[keyi]);
    return left;
}
//挖坑法
int PartSort2(vector<int>& v,int left,int right)
{
    int mini = GetMidIndex(v,left,right);
    swap(v[mini],v[left]);
    int key = v[left];
    int pivot = left;//左边作为坑 ->右边先走
    while(left < right)
    {
        //右边找比key严格小的,找到了之后放到坑位,然后right位置变为新坑
        while(left < right && v[right] >= key) 
            right--;
        swap(v[right],v[pivot]);
        pivot = right;
        //左边找比key严格大的,找到了之后放到坑位,然后left位置变为新坑
        while(left < right && v[left] <= key)
            left++;
        swap(v[left],v[pivot]);
        pivot = left;
    }
    //最后把key的值放到坑位上
    v[pivot]  = key;
    return pivot;
}
//前后指针法
int PartSort3(vector<int>& v,int left,int right)
{
    int mini = GetMidIndex(v,left,right);
    swap(v[mini],v[left]);
    int keyi = left;//左边作为key
    int prev = keyi;//[0,prev]标志的元素是比v[keyi]小的
    int cur = prev+1;//往后走,严格找比v[keyi]小的,然后和++prev交换,cur往后走继续找

    //版本1
    /*while(cur <= right)
    {
        while(cur <= right &&v[cur] >= v[keyi])
            cur++;
        if(cur <= right)
            swap(v[cur++],v[++prev]);
    }*/
    //版本2
    /*while(cur <= right)
    {
        if(v[cur] < v[keyi]) //cur找比v[keyi]小的
            swap(v[cur],v[++prev]);
        cur++;
    }*/
    //版本3-再优化
    while(cur <= right)
    {
        if(v[cur] < v[keyi] && cur != ++prev)//如果cur和++prev的指向是一样的,就不处理
            swap(v[cur],v[prev]); // prev在上面和cur判断的时候已经移动了
        cur++;
    }
    //最后把v[keyi]和v[prev]交换,返回prev位置
    swap(v[keyi],v[prev]);
    return prev;
}
void QuickSort(vector<int>& v,int left,int right)
{
    if(left >= right)
        return ;

    //小区间优化 [left,right]元素个数为:right-left+1
    if(right - left + 1 <= 10)
    {
        InsertSort_QuickSort(v,left,right);
    }
    else
    {
        int keyi = PartSort3(v,left,right);
        //[left,keyi-1]keyi[keyi+1,right]
        QuickSort(v,left,keyi-1);
        QuickSort(v,keyi+1,right);
    }
}



// //版本2-快排三路划分  <key =key >key
/*void QuickSort_2(vector<int>& v,int begin,int end)
{
    if(begin >= end)
        return ;

    //小区间优化 [begin,end]元素个数为:begin-end+1
    if(begin - end +1 <= 10)
    {
        InsertSort_QuickSort(v,begin,end);
    }
    else
    {
        int mid = GetMidIndex(v,begin,end);
        swap(v[begin],v[mid]);
        //left:标记<key的元素应该存放的位置  right:标记>key的元素应该存放的位置
        //[begin,left-1]就是<key的区域 [right+1,end]就是>key的区域 [left,right]就是=key的区域
        int left = begin,right = end;
        int key = v[left];//以左边的值作为划分对象
        int cur = begin + 1;
        while(cur <= right) //当cur>right结束
        {
            if(v[cur] < key)
            {
                swap(v[cur++],v[left++]);
            }
            else if(v[cur]  > key)
            {
                swap(v[cur],v[right--]); //需要继续考察交换过来的这个元素,cur不能++
            }
            else//v[cur] == key
                cur++;
        }
        //[begin,left-1][left,right][right+1,end]
        QuickSort_2(v,begin,left-1);
        QuickSort_2(v,right+1,end);
    }
}*/

int* PartSort(vector<int>& v,int left,int right)
{
    if(left == right) //只有一个数
        return new int[2]{left,right};
    int less = left-1; //标记<区域的右边界 [left,less]
    int more = right;//标记>区域的左边界  [more,right]
    int PartitionValue = v[right];//以v[right]作为划分值
    int cur = left;
    while(cur < more) //当cur和 >区域的左边界more相遇就退出
    {
        if(v[cur] > PartitionValue)
            swap(v[cur],v[--more]); //把v[cur]放到大于区域, cur不能动,还需要继续考察交换过来的这个数
        else if(v[cur] < PartitionValue)
            swap(v[cur++],v[++less]); //把v[cur]放到小于区域
        else //v[cur] == PartitionValue  cur往后走
            cur++;
    }
    swap(v[right],v[more]); //划分值和大于区域的第一个数交换,这样的话[less+1,more]就是 等于v[right]的区域
    return new int[2]{less+1,more};
}
//三路划分
void QuickSort_2(vector<int>& v,int left,int right)
{
    if(left >= right)
        return ;
    if(right - left +1 < 10)
    {
        InsertSort_QuickSort(v,left,right);
    }
    else
    {
        //结合随机选数
        int mid = GetMidIndex(v,left,right);
        swap(v[mid],v[right]);//和最右边的值交换
        //PartSort以最右边的值为划分值,返回的是 等于arr[right]的区域的范围 [equalArea[0],equalArea[1]]
        int* equalArea = PartSort(v,left,right);
        //[left,equalArea[0]-1] [equalArea[1] + 1,right]
        QuickSort_2(v,left,equalArea[0]-1);
        QuickSort_2(v,equalArea[1]+1,right);
    }
}


#include<stack>
void QuickSortNonR(vector<int>& v,int left,int right)
{
    if(left >= right)
        return ;
    stack<int> st;
    //注意栈的特性：后进先出
    //先压入右区间.再压入左区间 =>先拿到的就是左区间
    st.push(right);
    st.push(left);
    while(!st.empty()) //栈不为空,就说明还有区间需要处理
    {
        int begin = st.top();st.pop();
        int end = st.top();st.pop();
        int keyi = PartSort1(v,begin,end);
        //[begin,keyi-1][keyi+1,end]
        //判断区间是否合法,先押入右再压入左,先归并哪部分无所谓
        if(keyi-1 > begin) //一个数不归并
        {
            st.push(keyi-1);
            st.push(begin);
        }
        if(end > keyi+1)
        {
            st.push(right);
            st.push(keyi+1);
        }
    }
}

void _MergeSort(vector<int>& v,int left,int right,vector<int>& tmp)
{
  if(left >= right)
      return ;
  int mid = left + (right-left)/2;
  //1.递归让左右区间有序
  //[left,mid] [mid+1,right]
  _MergeSort(v,left,mid,tmp);
  _MergeSort(v,mid+1,right,tmp);
  //2.归并
  int begin1 = left,end1 = mid;
  int begin2 = mid+1,end2 = right;
  int index = left;//注意index的初始化不是0
  while(begin1<=end1 && begin2 <= end2)
  {
    if(v[begin1] <= v[begin2]) //谁小拷贝谁,相等的时候先拷贝左边的,保证稳定性
      tmp[index++] = v[begin1++];
    else 
      tmp[index++] = v[begin2++];
  }
  //下面两个while循环只会执行其中一个
  while(begin1 <= end1)
    tmp[index++] = v[begin1++];
  while(begin2 <= end2)
    tmp[index++] = v[begin2++];

  //将tmp数组的内容[left,right]拷贝回去
  for(int i = left;i<=right;i++)
    v[i] = tmp[i];
}
//归并排序
void MergeSort(vector<int>& v)
{
  vector<int> tmp(v.size(),0); 
  _MergeSort(v,0,v.size()-1,tmp);
}

//版本1--每次归并一组之后,就把部分数据拷贝回去
//[begin1,end1][begin2,end2] 
//case1:end1越界:不需要处理了,因为begin1~n-1位置的元素已经有序
//case2:begin2越界:不需要处理了,因为[begin1,end1]区间的元素是有序的
//case3:end2越界:需要处理,此时[begin2,n-1]的元素需要处理->两个区间都有值 修正end2位置为n-1
void MergeSortNonR(vector<int>& v)
{
    int n = v.size();
    vector<int> tmp(n,0);
    int gap = 1;
    while(gap < n)  //gap表示gap个元素和gap个元素之间进行归并
    {
        //当gap为1的时候: [0,0]和[1,1] [2,2]和[3,3] ...区间的元素分别进行归并
        //当gap为2的时候: [0,1]和[2,3] [4,5]和[6,7] ...区间的元素分别进行归并
        //规律 ：[i,i+gap-1] [i+gap,i+2*gap-1]   i+=2*gap:来到下一个应该归并的左区间的起始位置
        for(int i = 0;i<n;i += 2*gap) //注意：i+=2*gap  i代表的是每一组归并的左区间的起始位置 end2代表的是右区间的末尾位置
        {
            int begin1 = i,end1 = i+gap-1;
            int begin2 = i+gap,end2 = i+2*gap-1;
            //注意越界情况
            if(end1 >= n || begin2 >= n)
                break;
            if(end2 >= n) end2 = n-1;
            int index = i;//注意index的初始化不是0
            while(begin1<=end1 && begin2 <= end2)
            {
                if(v[begin1] <= v[begin2]) //谁小拷贝谁,相等的时候先拷贝左边的,保证稳定性
                    tmp[index++] = v[begin1++];
                else 
                    tmp[index++] = v[begin2++];
            }
            while(begin1 <= end1)
                tmp[index++] = v[begin1++];
            while(begin2 <= end2)
                tmp[index++] = v[begin2++];

            //版本1:每组归并完就拷贝回去,注意此时拷贝的范围是:[i,end2]
            for(int j = i;j<=end2;j++)
                v[j] = tmp[j];
        }
        gap *=2; // 由11归并->22归并->44归并.... 
    }
}

//版本2--整个组别归并完成之后,把全部数据拷贝回去
//[begin1,end1] [begin2,end2]
//case1：end1越界 ->[begn2,end2]不存在  只需修正end1的下标为n-1
//case2: begin2越界 --> 让[begin2,end2]区间不存在,即让begin2 > end2
//case3: end2越界  ->修正end2的下标为n-1
void MergeSortNonR_2(vector<int>& v)
{
    int n = v.size();
    int gap = 1; 
    vector<int> tmp(n,0);
    while(gap < n)
    {
        for(int i = 0;i<n;i += 2*gap)
        {
            //[i,i+gap-1] [i+gap,i + 2*gap -1]
            int begin1 = i,end1 = i + gap -1;
            int begin2 = i + gap,end2 = i + 2*gap -1;
            int index = i;//注意index的初始值 
            //注意越界情况
            if(end1 >= n ) end1 = n-1;
            if(begin2 >= n)  begin2 = n,end2 = n-1;
            if(end2 >= n) end2 = n-1;
            while(begin1<=end1 && begin2 <= end2)
            {
                if(v[begin1] <= v[begin2])
                    tmp[index++] = v[begin1++];
                else
                    tmp[index++] = v[begin2++];
            }
            while(begin1 <= end1)
                tmp[index++] = v[begin1++];
            while(begin2 <= end2)
                tmp[index++] = v[begin2++];
        }
        //假设gap为1 :那么就是全部11归并完成之后再拷贝 ....
        for(int i = 0;i<n;i++) //拷贝n个数据
            v[i] = tmp[i];
        gap *= 2; 
    }
}

//计数排序
//绝对映射 ->缺陷:针对负数不好处理
void CountSort_version1(vector<int>& v)
{
    //1.找出数组的最大值
    int max = v[0];
    for(int i = 0;i<v.size();i++)
    {
        if(v[i] > max) 
            max = v[i];
    }
    //2.开辟max+1个空间
    vector<int> Count(max+1,0);
    //3.进行绝对映射,统计出现次数
    for(int i = 0;i<v.size();i++)
    {
        Count[v[i]]++;
    }
    //4.遍历[0,max],根据元素出现次数,放回原数组
    //Count[i]:值为i的元素的出现次数
    int index = 0;
    for(int i = 0;i<=max;i++)
    {
        while(Count[i] > 0)
        {
            v[index++] = i;
            Count[i]--;
        }
    }
}
//相对映射
void CountSort_version2(vector<int>& v)
{
    //1.找出最大最小值
    int max = v[0],min = v[0];
    for(int i = 1;i<v.size();i++)
    {
        if(v[i] > max) max = v[i];
        if(v[i] < min) min = v[i];
    }
    //2.元素范围是[min,max] 二者可能都是负数,但是不影响  开辟max-min+1个空间
    int range = max - min + 1;
    vector<int> Count(range,0);
    //3.进行相对映射  v[i]映射在Count数组的:v[i] - min位置
    for(int i = 0;i<v.size();i++)
    {
        Count[v[i] - min]++;
    }
    //4.放回原数组  -相对映射
    //Count[i]:代表i + min元素出现的次数
    int index = 0;
    for(int i = 0;i < range;i++) //Count共有range个元素,下标范围是0~range-1
    {
        while(Count[i] > 0)
        {
            v[index++] = i + min;
            Count[i]--;
        }
    }
}